package org.misty.practices.algorithm.tree;

import java.nio.CharBuffer;
import java.util.ArrayList;
import java.util.LinkedList;

public class BiTree {
    private char data;
    private BiTree left;
    private BiTree right;

    public BiTree() {
    }

    public BiTree(char data) {
        this.data = data;
    }

    protected void setData(char c) {
        this.data = c;
    }

    protected void setLeft(BiTree left) {
        this.left = left;
    }

    protected void setRight(BiTree right) {
        this.right = right;
    }

    public char getData() {
        return this.data;
    }

    public BiTree getLeft() {
        return this.left;
    }

    public BiTree getRight() {
        return this.right;
    }

    @Override
    public String toString() {
        return "BiTree{ " + preOrderTraverse(this) + " }";
    }

    public static BiTree create(String seq) {
        var buffer = CharBuffer.wrap(seq);
        return buffer.hasRemaining() ? create0(buffer) : null;
    }

    private static BiTree create0(CharBuffer buffer) {
        char ch = buffer.get();
        if (ch == '#') {
            return null;
        } else {
            var t = new BiTree(ch);
            if (buffer.hasRemaining()) t.setLeft(create0(buffer));
            if (buffer.hasRemaining()) t.setRight(create0(buffer));
            return t;
        }
    }

    /* 广度优先算法 */
    public static String breadthFirst(BiTree tree) {
        var buffer = new StringBuilder();
        var list = new LinkedList<BiTree>();
        list.offerLast(tree);
        while (list.size() > 0) {
            var node = list.pollFirst();
            if (node != null) {
                buffer.append(node.data);
                list.offerLast(node.left);
                list.offerLast(node.right);
            }
        }
        return buffer.toString();
    }

    /* 前序遍历 */
    public static String preOrderTraverse(BiTree tree) {
        var buffer = new StringBuilder(10);
        preOrderTraverse0(tree, buffer);
        return buffer.toString();
    }

    private static void preOrderTraverse0(BiTree tree, StringBuilder buffer) {
        if (tree == null) {
            buffer.append('#');
        } else {
            buffer.append(tree.data);
            preOrderTraverse0(tree.left, buffer);
            preOrderTraverse0(tree.right, buffer);
        }
    }


    /* 中序遍历 */
    public static String inOrderTraverse(BiTree tree) {
        var buffer = new StringBuilder(10);
        inOrderTraverse0(tree, buffer);
        return buffer.toString();
    }

    private static void inOrderTraverse0(BiTree tree, StringBuilder buffer) {
        if (tree == null) {
            buffer.append('#');
        } else {
            inOrderTraverse0(tree.left, buffer);
            buffer.append(tree.data);
            inOrderTraverse0(tree.right, buffer);
        }
    }

    /* 后序遍历 */
    public static String postOrderTraverse(BiTree tree) {
        var buffer = new StringBuilder(10);
        postOrderTraverse0(tree, buffer);
        return buffer.toString();
    }

    private static void postOrderTraverse0(BiTree tree, StringBuilder buffer) {
        if (tree == null) {
            buffer.append('#');
        } else {
            postOrderTraverse0(tree.left, buffer);
            postOrderTraverse0(tree.right, buffer);
            buffer.append(tree.data);
        }
    }

    public static void main(String[] args) {
        var tree = create("AB#D##C##");
        System.out.println(tree);
        System.out.println(inOrderTraverse(tree));
        System.out.println(postOrderTraverse(tree));
        System.out.println(breadthFirst(tree));
    }
}
